# -*- coding: utf-8 -*-

# 给定一个非负整数数组，你最初位于数组的第一个位置

# 数组中的每个元素代表你在该位置可以跳跃的最大长度

# 你的目标是使用最少的跳跃次数到达数组的最后一个位置

# 示例:
# 输入: [2,3,1,1,4]
# 输出: 2

# 解释: 跳到最后一个位置的最小跳跃数是 2。
#      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置

# 说明:
# 假设你总是可以到达数组的最后一个位置

# # 能够解出答案，但是算法超时了
# # 时间复杂度 n平方
# class Solution(object):
#     def jump(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         step = [len(nums) + 1] * len(nums);
#         step[0] = 0;

#         for i in xrange(0, len(nums) - 1):
#             for j in xrange(1, nums[i] + 1):
#                 if i + j > len(nums) - 1:
#                     continue;
#                 if step[i] + 1 < step[i + j]:
#                     step[i + j] = step[i] + 1;
        
#         return step[len(nums) - 1];

# t = Solution();
# print t.jump([25000,24999,24998,24997,24996,24995,24994,24993,24992,24991,24990,24989,24988,24987,24986,24985,24984,24983,24982,24981,24980,24979,24978,24977,24976,24975,24974,24973,24972,24971,24970,24969,24968,24967,24966,24965,24964,24963,24962,24961,24960,24959,24958,24957,24956,24955,24954,24953,24952,24951,24950,24949,24948,24947,24946,24945,24944,24943,24942,24941,24940,24939,24938,24937,24936,24935,24934,24933,24932,24931,24930,24929,24928,24927,24926,24925,24924,24923,24922,24921,24920,24919,24918,24917,24916,24915,24914,24913,24912,24911,24910,24909,24908,24907,24906,24905,24904,24903,24902,24901,24900,24899,24898,24897,24896,24895,24894,24893,24892,24891,24890,24889,24888,24887,24886,24885,24884,24883,24882,24881,24880,24879,24878,24877,24876,24875,24874,24873,24872,24871,24870,24869,24868,24867,24866,24865,24864,24863,24862,24861,24860,24859,24858,24857,24856,24855,24854,24853,24852,24851,24850,24849,24848,24847,24846,24845,24844,24843,24842,24841,24840,24839,24838,24837,24836,24835,248]);
# 
# 
# 
# 
# 
# 
# 
# 
# 
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if(len(nums) <= 1):
            return 0;

        i = 0;
        step = 1;
        # locus = [0];
        while i + nums[i] < len(nums) - 1:
            step += 1;
            energy = nums[i];

            j = i;
            max = 0;
            next = i + 1;
            while energy:
                energy -= 1;
                j = j + 1;
                if nums[j] + j - i > max:
                    max = nums[j] + j - i;
                    next = j

            i = next;
            # locus.append(i);

        # print locus;
        return step;



t = Solution();
# print t.jump([2,3,1,1,4]);
print t.jump([0]);